#include <iostream>
#include <vector>

using namespace std;

// 100.00 %
class Solution1
{
  public:
	vector<string> letterCombinations(string digits)
	{
		vector<string> res;
		if (digits == "")
			return res;
		string letter = getCharacter(digits[0]);
		for (int i = 0; i < letter.length(); i++)
		{
			vector<string> rest = letterCombinations(digits.substr(1));
			if (rest.size() == 0)
				res.push_back(letter.substr(i, 1));
			else
				for (int j = 0; j < rest.size(); j++)
				{
					res.push_back(letter.substr(i, 1) + rest[j]);
				}
		}
		return res;
	}
	string getCharacter(char n)
	{
		switch (n)
		{
		case '2':
			return "abc";
		case '3':
			return "def";
		case '4':
			return "ghi";
		case '5':
			return "jkl";
		case '6':
			return "mno";
		case '7':
			return "pqrs";
		case '8':
			return "tuv";
		case '9':
			return "wxyz";
		default:
			return "";
		}
	}
};

class Solution
{
  private:
	const string letterMap[10] = {
		" ",
		"",
		"abc",
		"def",
		"ghi",
		"jkl",
		"mno",
		"pqrs",
		"tuv",
		"wxyz"};
	vector<string> res;
	void findCombination(const string &digits, int index, const string &s)
	{
		if (index == digits.size())
		{
			res.push_back(s);
			return;
		}
		char c = digits[index];
		string letters = letterMap[c - '0'];
		for (int i = 0; i < letters.length(); i++)
		{
			findCombination(digits, index + 1, s + letters[i]);
		}
	}

  public:
	vector<string> letterCombinations(string digits)
	{
		res.clear();
		if (digits == "")
			return res;
		findCombination(digits, 0, "");
		return res;
	}
};

int main()
{
	string d = "23";
	vector<string> res = Solution().letterCombinations(d);
	cout << res.size() << endl;
	for (int i = 0; i < res.size() - 1; i++)
	{
		cout << res[i] << " ";
	}
	cout << res[res.size() - 1] << endl;
}